import java.util.*;

class Interview17_13 {

    // 恢复空格

    public static int respace(String[] dictionary, String sentence) {
        if (sentence.length() <= 0)
            return 0;
        int[] dp = new int[sentence.length()+1];
        Map<Integer, List<Integer>> count = new HashMap<>();
        for (String val : dictionary) {
            int start = 0;
            int pos = sentence.indexOf(val, start);
            while (pos > -1) {
                int end = pos + val.length() - 1;
                List<Integer> list = count.getOrDefault(end, new ArrayList<>());
                list.add(pos);
                count.put(end, list);
                pos = sentence.indexOf(val, end+1);
            }
        }

        for (int i = 1; i <= sentence.length(); i++) {
            dp[i] = dp[i - 1] + 1;
            if (!count.containsKey(i-1)) {
                continue;
            }
            for (Integer val : count.get(i-1)) {
                dp[i] = Math.min(dp[i], dp[val]);
            }
        }
        return dp[sentence.length()];
    }
    public static void main(String[] args) {
        String[] dictionary = {"looked","just","like","her","brother"};
        String sentence = "jesslookedjustliketimherbrother";
        System.out.println(respace(dictionary, sentence));
    }
}